//函数递归
#include <stdio.h>
//1️⃣接受一个整型值（无符号），按照顺序打印它的每一位
//例如：输入：1234 输出：1 2 3 4
//思路：
int main()
{
    unsigned int num=0;
    scanf("%u",&num);
    while(num)     //当num为0时循环终止
    {
        printf("%u ",num%10);
        num=num/10;
    }
    return 0;
}   //输出：4 3 2 1
//函数递归的实现：
void print(unsigned int n)
{
    if(n>9)
    {
        print(n/10);
    }
    printf("%u ",n%10);
}
int main()
{
    unsigned int num=0;
    scanf("%u",&num);
    print(num);
    return 0;
}   //输入：1234输出：1 2 3 4     输入：12345输出：1 2 3 4 5

//2️⃣编写函数不允许创建临时变量，求字符串的长度(模拟实现strlen)
//思路：（有临时变量）
#include <string.h>
//也可以写成：int my_strlen(char str[]) 参数部分为数组形式
int my_strlen(char* str) //参数部分为指针形式
{
    int count=0;
    while(*str!='\0')
    {
        count++; //计数，临时变量
        str++; //找下一个字符，++变为下一个字符地址
    }
    return count;
}
int main()
{
    char arr[]="abc"; //[a b c \0]
    int len=my_strlen(arr);
    printf("%d\n",len);
    return 0;
}
//函数递归实现：
int my_strlen(char* str)
{
    if(*str!='\0')
    return 1+my_strlen(str+1); //不能写成str++ 因为先返回后++
    else 
    return 0;
}
int main()
{
    char arr[]="abc";
    int len=my_strlen(arr);
    printf("%d\n",len);
    return 0;
}
//指针-指针方法实现 见8.c P85

//递归与迭代
//3️⃣求n的阶乘（不考虑溢出） 
//迭代的方式   见11.c
//递归实现
int factorial(int n)
{
    if(n<=1)
    return 1;
    else
    return n*factorial(n-1);
}
int main()
{
    int n;
    scanf("%d",&n);
    int ret=factorial(n);
    printf("%d\n",ret);
    return 0;
}

//4️⃣求第n个斐波那契数（不考虑溢出）
//1 1 2 3 5 8 13 21 34……
//递归实现（效率很低）
//int count=0;  全局变量
int F(int n)
{
    //if(n==0)
    //return 0;
    //else if(n==1)
    //return 1;
    if(n<=2)
    return 1;
    else
    return F(n-1)+F(n-2);
    //if(n==3)
    //count++;
}
int main()
{
    int n;
    scanf("%d",&n);
    int ret=F(n);
    printf("%d\n",ret);
    return 0;
}
//迭代(效率高)
int F(int n)
{
    int a=1;
    int b=1;
    int c=1; //初始化为1，当n<3时直接返回c值，也就是1。
    while(n>=3)
    {   
        c=a+b; 
        a=b;
        b=c;
        n--;
    }
    return c;
}
int main()
{
    int n;
    scanf("%d",&n);
    int ret=F(n);
    printf("%d\n",ret);
    return 0;
} 
//⚠️小乐需要走n阶台阶，每次可以选择走一阶或者走两阶，那么他一共有多少种走法？
//斐波那契系问题（走台阶、青蛙跳、汉诺塔、兔子繁衍等）
//分析：1个台阶，1种走法；2个台阶，2种走法
//当n>2时，走第一步时有两种选择：若是走1阶，还有(n-1)阶；若是走2阶，还有(n-2)阶
//n个台阶有f(n)种走法，同理选第一种后还有f(n-1)种走法；选第二种后还有f(n-2)种走法  
//f(n)=f(n-1)+f(n-2) (n>2)
int f(int n)
{
    if(n<=2)
    return n;
    else
    return f(n-1)+f(n-2);
}
int main()
{
    int n;
    scanf("%d",&n);
    int ret=f(n);
    printf("%d\n",ret);
    return 0;
}

//5️⃣字符串逆序
//循环
#include <string.h>
int main()
{
    char arr[]="abcdefg";
    int len=strlen(arr);
    int left=0; 
    int right=len-1;
    char m;
    while(left<right)
    {
        m=arr[left];
        arr[left]=arr[right];
        arr[right]=m;
        left++;
        right--;
    }
    printf("%s\n",arr);
    return 0;
}
//递归 方法一：只有一个参数
#include <string.h>
void reverse_string(char* str)
{
    int len=strlen(str);
    char m=*str;
    *str=*(str+(len-1));
    *(str+(len-1))='\0';  //为了中间形成字符串
    if(len>3) //strlen(str+1)>1 限制条件是至少中间还有两个字符
    {
        reverse_string(str+1);
    }
    *(str+(len-1))=m;
}
int main()
{
    char arr[]="abcde fg";
    //scanf("%s",arr);
    gets(arr);//为了读取空格
    reverse_string(arr);
    printf("%s\n",arr);
    return 0;
}
//递归 方法二：有多个参数
#include <string.h>
void reverse_string(char arr[],int left,int right)
{
   char m=arr[left];
   arr[left]=arr[right];
   arr[right]=m;
   if(left+1<right-1)  //限制条件是中间存在至少两个字符
   {
    reverse_string(arr,left+1,right-1);
   }
}
int main()
{
    char arr[]="abcdefg";
    scanf("%s",arr);
    int len=strlen(arr);
    int left=0;
    int right=len-1;
    reverse_string(arr,left,right);
    printf("%s\n",arr);
    return 0;
}

//6️⃣计算一个数的每位之和
//DigitSum(1234)
//DigitSum(123)+4
//DigitSum(12)+3+4
//DigitSum(1)+2+3+4
int DigitSum(unsigned int n)
{
    int m=0;
    if(n>0)                       //if(n>9)
    {                             //  return DigitSum(n/10)+n%10;
        m=DigitSum(n/10)+n%10;    //else
    }                             //  return n;
    return m;
}
int main()
{
    unsigned int n=1234;
    scanf("%u",&n);
    int sum=DigitSum(n);
    printf("%d\n",sum);
    return 0;
}

//7️⃣实现n的k次方 (整数次方)
//((((n)*n)*n)*n)*n……
//k>0  n*n的k-1次方     ——>Pow(n,k-1)*n
//k=0  1                    
//k<0  n的k次方分之一  ——>1.0/Pow(n,-k)
double Pow(int n,int k)
{
   if(k==0)
    return 1;
   else if(k>0)
   {
    return Pow(n,k-1)*n;
   }
   else
   {
    return 1.0/Pow(n,-k);  //注意返回值类型
   }
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    double ret=Pow(n,k);
    printf("%lf\n",ret);
    return 0;
}
//库函数中求n的k次方的函数:pow(n,k) （可用msdn查看）

//8️⃣杨辉三角
int triangle(int i,int j)
{
    if(j==1||j==i)
    return 1;
    else 
    return triangle(i-1,j-1)+triangle(i-1,j);
}
int main() 
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            printf("%5d",triangle(i,j));
        }
        printf("\n");
    }
    return 0;
}